#include "sort.h"

#define swap(a,b) do{typeof(a) t=a;a=b;b=t;}while(0)
#define min(a,b) ((a)<(b)?(a):(b))

void show_sort_res(const char* name, int* arr, size_t len)
{
    printf("%s:", name);
    for (int i = 0; i < len; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void select_sort(int* arr, size_t len)
{
    show_sort_res("未排序", arr, len);
    for (int i = 0; i < len - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < len; j++)
        {
            if (arr[j] < arr[min])
            {
                min = j;
            }
        }
        if (min != i)
        {
            swap(arr[min], arr[i]);
        }
    }
    show_sort_res("选择排序", arr, len);
}

void bubble_sort(int* arr, size_t len)
{
    show_sort_res("未排序", arr, len);
    bool flag = true;
    for (int i = len - 1; i > 0 && flag; i--)
    {
        flag = false;
        for (int j = 0; j < i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(arr[j], arr[j + 1]);
                flag = true;
            }
        }
    }
    show_sort_res("冒泡排序", arr, len);
}

void insert_sort(int* arr, size_t len)
{
    show_sort_res("未排序", arr, len);
    for (int i = 1, j; i < len; i++)
    {
        int tmp = arr[i];
        for (j = i - 1; j >= 0 && tmp < arr[j]; j--)
        {
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = tmp;
    }
    show_sort_res("插入排序", arr, len);
}

void shell_sort(int* arr, size_t len)
{
    show_sort_res("未排序", arr, len);
    for (int k = len / 2; k > 0; k /= 2)
    {
        for (int i = k, j; i < len; i++)
        {
            int tmp = arr[i];
            for (j = i - k; j >= 0 && tmp < arr[j]; j -= k)
            {
                arr[j + k] = arr[j];
            }
            arr[j + k] = tmp;
        }
    }
    show_sort_res("希尔排序", arr, len);
}

static void createHeap(int* arr, size_t len, int root)
{
    while (root * 2 <= len)
    {
        int max = root * 2;
        if (max + 1 < len && arr[max - 1] < arr[max])
        {
            max++;
        }
        if (arr[root - 1] > arr[max - 1])
        {
            return;
        }
        swap(arr[root - 1], arr[max - 1]);
        root = max;
    }
}

void heap_sort(int* arr, size_t len)
{
    show_sort_res("未排序", arr, len);
    for (int i = len / 2; i > 0; i--)
    {
        createHeap(arr, len, i);
    }
    for (int i = len - 1; i > 0; i--)
    {
        swap(arr[0], arr[i]);
        createHeap(arr, i, 1);
    }
    show_sort_res("堆排序", arr, len);
}

int size;

static void _quickSortStack(int* arr, int left, int right)
{
    //show_sort_res("开始排序",arr,size);
    if (left >= right)
        return;
    int len = right - left + 1;
    int tmp[len];
    int pv = arr[left];
    int l = 0, r = len - 1;
    for (int i = left + 1; i <= right; i++)
    {
        if (arr[i] < pv)
        {
            tmp[l++] = arr[i];
        }
        else
        {
            tmp[r--] = arr[i];
        }
    }
    tmp[l] = pv;
    memcpy(arr + left, tmp, len * sizeof(arr[0]));
    //sleep(1);
    _quickSortStack(arr, left, left + l - 1);
    _quickSortStack(arr, left + l + 1, right);
}

static void _quickSort(int* arr, int left, int right)
{
    if (left >= right)
        return;
    int pi = left, pv = arr[left];
    for (int l = left, r = right; l < r;)
    {
        //show_sort_res("开始排序",arr,size);
        //sleep(1);
        while (l < r && pv <= arr[r]) r--;
        if (l < r)
        {
            arr[pi] = arr[r];
            //printf("修改arr[%d]和arr[%d],l=%d,r=%d\n",pi+1,r+1,l+1,r+1);
            pi = r;
        }
        //show_sort_res("左边排序",arr,size);
        while (l < r && pv > arr[l]) l++;
        if (l < r)
        {
            arr[pi] = arr[l];
            //printf("修改arr[%d]和arr[%d],l=%d,r=%d\n",pi+1,l+1,l+1,r+1);
            pi = l;
        }
        //show_sort_res("右边排序",arr,size);
    }
    //printf("还原标杆arr[%d]的值%d\n",pi+1,pv);
    arr[pi] = pv;
    //printf("下一轮排序范围 %d,%d %d,%d\n",left+1,pi,pi+2,right+1);
    //sleep(1);
    _quickSort(arr, left, pi - 1);
    _quickSort(arr, pi + 1, right);
}

void quick_sort(int* arr, size_t len)
{
    show_sort_res("未排序\t", arr, len);
    size = len;

    _quickSort(arr, 0, len - 1);

    show_sort_res("快速排序", arr, len);
}

void quick_sort_stack(int* arr, size_t len)
{
    show_sort_res("未排序\t", arr, len);
    size = len;

    _quickSortStack(arr,0,len-1);

    show_sort_res("快速排序", arr, len);
}

void merge_sort(int* arr, size_t len)
{
    show_sort_res("未排序\t", arr, len);
    int* dest = malloc(sizeof(arr[0] * len)), * src = arr;
    for (int k = 1; k < len; k *= 2)
    {
        for (int i = 0, j; i < len; i += k * 2)
        {
            int s1 = j = i, e1 = min(i + k, len);
            int s2 = min(i + k, len), e2 = min(i + k * 2, len);
            while (s1 < e1 && s2 < e2) dest[j++] = src[s1] < src[s2] ? src[s1++] : src[s2++];
            while (s1 < e1) dest[j++] = src[s1++];
            while (s2 < e2) dest[j++] = src[s2++];
        }
        //show_sort_res("归并排序",dest,len);
        swap(dest, src);
    }
    if (src != arr) {
        memcpy(arr, src, sizeof(arr[0]) * len);
        dest = src;
    }
    free(dest);
    show_sort_res("归并排序", arr, len);
}

void count_sort(int* arr, size_t len)
{
    show_sort_res("未排序", arr, len);
    int max = arr[0], min = arr[0];
    for (int i = 1; i < len;i++) {
        if (max < arr[i]) max = arr[i];
        if (min > arr[i]) min = arr[i];
    }
    int size = max - min + 1;
    //int count[size];
    //bzero(count,sizeof(arr[0]) * size);
    int* count = calloc(sizeof(arr[0]), size);
    for (int i = 0; i < len;i++) {
        count[arr[i] - min]++;
    }
    for (int i = 0, k = 0; i < size;i++) {
        for (int j = 0; j < count[i]; j++) {
            arr[k++] = i + min;
        }
    }
    free(count);
    show_sort_res("计数排序", arr, len);
}

void radix_sort(int* arr, size_t len)
{
    show_sort_res("未排序\t", arr, len);
    int count[10];
    int data[len];
    //先获取循环次数
    int k = 0, m = 1;
    for (int i = 0; i < len; i++) {
        while (arr[i] > m) {
            m *= 10;
            k++;
        }
    }
    //当前位数
    int radix = 1;
    for (int i = 0;i < k;i++) {
        //每次过后应该清空
        bzero(count, sizeof(count[0]) * 10);
        //统计数字对应位数
        for (int j = 0;j < len;j++) {
            k = (arr[j] / radix) % 10;
            count[k]++;
        }
        //桶

        printf("当前桶:");
        for (int j = 1;j < 10;j++) {
            printf("%d ", count[j]);
        }
        printf("\n");

        for (int j = 1;j < 10;j++) {
            count[j] += count[j - 1];
        }

        printf("当前桶:");
        for (int j = 1;j < 10;j++) {
            printf("%d ", count[j]);
        }
        printf("\n");

        for (int j = len - 1; j >= 0; j--) {
            k = (arr[j] / radix) % 10;
            data[count[k] - 1] = arr[j];
            count[k]--;
        }
        memcpy(arr, data, len * sizeof(arr[0]));
        radix *= 10;
    }
    show_sort_res("基数排序", arr, len);
}
